package com.cdy.demo.algorithm;

public class Leetcode121 {

    public static void main(String[] args) {
        Leetcode121 leetcode121 = new Leetcode121();
        System.out.println( leetcode121.maxProfit(2, new int[]{2,4,1}));
    }

    /**
     * 121
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {

        int len = prices.length;

        if (len ==0 ) return 0;

        // dp[i][0]代表 第i+1天时股票为空
        // dp[i][1]代表 第i+1天时股票不为空
        int[][] dp = new int[len + 1][2];

        dp[0][0]=0;
        dp[0][1]=Integer.MIN_VALUE;

        int maxProfit = 0;
        for (int i = 1; i < len + 1; i++) {
            //第i天 没有持有股票 -》 昨天也没有持有股票或者昨天持有今天我卖出股票
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i- 1]);
            //第i天 持有股票 -》 昨天持有股票， 第二种情况不存在因为只能交易一次
            dp[i][1] = Math.max(dp[i - 1][1], -prices[i- 1]);

            maxProfit = Math.max(maxProfit, dp[i][0]);
        }
        return maxProfit;

    }

    /**
     * 122
     * @param prices
     * @return
     */
    public int maxProfit2(int[] prices) {

        int len = prices.length;

        if (len ==0 ) return 0;

        // dp[i][0]代表 第i+1天时股票为空
        // dp[i][1]代表 第i+1天时股票不为空
        int[][] dp = new int[len + 1][2];

        dp[0][0]=0;
        dp[0][1]=Integer.MIN_VALUE;

        int maxProfit = 0;
        for (int i = 1; i < len + 1; i++) {
            //第i天 没有持有股票 -》 昨天也没有持有股票或者昨天持有今天我卖出股票
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i- 1]);
            //第i天 持有股票 -》 昨天持有股票，
            dp[i][1] = Math.max(dp[i - 1][1],dp[i - 1][0] -prices[i- 1]);

            maxProfit = Math.max(maxProfit, dp[i][0]);
        }
        return maxProfit;

    }

    /**
     * 188
     * @param prices
     * @return
     */
    public int maxProfit(int k, int[] prices) {

        int len = prices.length;

        if (len ==0 ) return 0;

        if (k> len/2) k = len / 2;

        // dp[i][0]代表 第i+1天时股票为空
        // dp[i][1]代表 第i+1天时股票不为空
        int[][][] dp = new int[len + 1][k+1][2];

        for (int i = 0; i < k+1; i++) {
            dp[0][i][0]=0;
            dp[0][i][1]=Integer.MIN_VALUE;
        }

        int maxProfit = 0;
        // j -> 买入算一次购买次数
        for (int i = 1; i < len + 1; i++) {
            for (int j = k;j>=1;j--) {
                //第i天 没有持有股票 -》 昨天也没有持有股票或者昨天持有今天我卖出股票
                dp[i][j][0] =Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i - 1]);
                //第i天 持有股票 -》 昨天持有股票， 第二种情况不存在因为只能交易一次
                dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j-1][0] -prices[i - 1]);
                maxProfit = Math.max(maxProfit, dp[i][j][0]);
            }
        }
        return maxProfit;

    }


    /**
     * 714
     * @param prices
     * @param fee
     * @return
     */
    public int maxProfit(int[] prices, int fee) {
        int len = prices.length;

        if (len ==0) return 0;


        long[][] dp = new long[len + 1][2];


        dp[0][0]=0;
        dp[0][1] = Integer.MIN_VALUE;

        long max = 0;
        for (int i = 1; i < len+1; i++) {

            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i - 1] - fee);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i - 1]);

            max = Math.max(max, dp[i][0]);
        }

        return (int)max;

    }
}
